﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

//循环链表经典应⽤：环形链表的约瑟夫问题：
//环形链表的约瑟夫问题
//描述：
//编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
//下一个人继续从 1 开始报数。
//n - 1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
//方法：
//对循环单链表遍历，每遍历m次删除一个数据
//数据范围：
//1≤n, m≤10000
//进阶：空间复杂度O(1)，时间复杂度O(n)
//示例1
//输入：
//5, 2
//返回值：
//3
//说明：
//开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
//1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
//1，3，5，从5开始报数，5->1，1->2编号为1的人离开
//3，5，从3开始报数，3->1，5->2编号为5的人离开
//最后留下人的编号是3


struct ListNode
{
    int val;
    struct ListNode* next;
};
//思路一：创建一个新链表，遍历原链表，小的头插，大的尾插


typedef struct ListNode ListNode;
//申请节点——创建一个节点并赋值
ListNode* BuyNode(int x)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    //可写可不写，一般不会申请失败
    //if (newNode == NULL) 
    //{
    //    exit(1);
    //}
    newNode->val = x;
    newNode->next = NULL;
    return newNode;
}
//创建链表——创建n个节点的不带头单向循环链表
ListNode* createList(int n)
{
    //创建第一个有效节点
    ListNode* phead = BuyNode(1);
    //头和尾都指向第一个有效节点
    ListNode* ptail = phead;
    //创建第2 至 n个有效节点
    for (int i = 2; i <= n; i++)
    {
        ptail->next = BuyNode(i);
        ptail = ptail->next;
    }
    //链表要首尾相连使其循环起来
    ptail->next = phead;
    //return phead;
    return ptail;//避免下面的prev为空
}
int ysf(int n, int m)
{
    //创建不带头单向循环链表
    //ListNode* head = createList(n);
    //ListNode* pcur = head;
    //ListNode* prev = NULL;//使用prev的弊端：当m=1，第一次进入循环就删除，但此时prev为NULL，没有next，就无法使前驱节点指向后续节点
    //解决办法: createList方法不返回头结点，而是返回尾结点。既能知道第一个节点的前驱节点，也能够通过尾结点找到第一个节点
    ListNode* prev = createList(n);//定义prev来接受尾结点指针
    ListNode* pcur = prev->next;

    //计数
    int count = 1;
    //逢m删除节点
    while (pcur->next != pcur)
    {
        if (count == m)
        {
            //删除当前节点pcur,
            prev->next = pcur->next;
            free(pcur);
            //删除pcur节点之后，要让pcur走到新的位置，count置为初始值
            pcur = prev->next;
            //重新计数
            count = 1;
        }
        else
        {
            //prev往后走
            prev = pcur;
            //pcur往后走
            pcur = pcur->next;
            //计数
            count++;
        }
    }
    //此时pcur结点就是幸存下来的唯一的一个节点
    return pcur->val;
}


void test1()
{
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", ysf(n, m));
}
int main()
{
    test1();
    return 0;
}



